For the processing of 16-bit real and 16-bit imaginary data there is a remarkable advantage of using the 4-bit-at-a-time (4BAAT) distributed arithmetic (DA) four-point discrete Fourier transform (DFT). It is known that by addressing the proper segments of read-only memories (ROMs) through pin programming, one device type can be used throughout an array of devices to make high-speed FFTs. Such one-chip high-speed FFTs also permit one-chip windowing, but the window coefficients in the ROM restrict both the size of the transform and the window type that may be implemented because of the limitations on memory size.
Referring to FIG. 1, a simplified block diagram of the configuration of a first tier device in a radix four decimate-in-time (DIT) FFT-device array is shown. Signals must be "windowed" to control artifacts introduced by the finite length of the digital signal data record.
In a decimate-in-time type device, windowing is performed by multiplying each input signal sample by a suitable real time-domain-weighting coefficient. The four inputs, labeled 0-3, are complex, and may be, for example, in 16-bit, 2's-complement, fixed-point format. Both the real data and the imaginary data are multiplied by a real window coefficient in the multiplier 11-14 coupled in each input line. Each multiplier block shown in FIG. 1 may consist of a pair of real multipliers, one for the real data, and one for the imaginary data. The complex four-point-DFT block 15 is a multiplier-free collection of adders. The output of the DFT consists of four complex outputs, each on its own output line. The output lines are then connected to the inputs of building blocks of subsequent tiers of the array.
FIG. 2 illustrates a building block that may be used in the second and subsequent stages or tiers of the FFT-device array. The difference between the building block of FIG. 2 and that of FIG. 1 is that the building block of FIG. 2 only requires three multipliers 21-23 on three of the input lines for implementing the "twiddle-factor" coefficients associated with the appropriate tier qr stage. But, those multipliers must be fully complex to implement those twiddle-factor coefficients.
The decimate-in-time structures of FIGS. 1 and 2 may be compared with the building blocks suitable for a decimate-in-frequency (DIF) FFT device shown in FIG. 3. In the DIF type device, the twiddle-factor multipliers 31-33 are on the output lines from the complex four-point DFT. An array of DIF transformers has slightly worse system computational noise that DIT transformers. This degradation in noise is generally found to be approximately three db.